#if !defined(_OBJPTRLIST_H__)
#define _OBJPTRLIST_H__

#if _MSC_VER >= 1000
#pragma once
#endif

typedef int (__cdecl *OBJPTRLISTCMPFUNC)(const void *ppElement1,const void *ppElement2);

template <class TYPE> class CObjPtrList
{
public:
	CObjPtrList(int cnExpand=10);
	virtual ~CObjPtrList();

	//set expanding count of element pointer buffer
	void SetExpandCount(int cnExpand=10, int cnTotal=0);
	BOOL CloneFrom(CObjPtrList<TYPE> &listSrc, int nHead = 0, int nTail = 0);

public:
	// count of element pointer
	int GetCount() const;
	int GetSize() const;;
	BOOL IsEmpty() const;

	// peek at head or tail
	TYPE *GetHead() const;
	TYPE *GetTail() const;

	// remove at head or tail
	BOOL RemoveHead();
	BOOL RemoveTail();

	// add before head or after tail
	BOOL AddHead(TYPE *pElement);
	BOOL AddTail(TYPE *pElement);

	// remove all element pointer
	BOOL RemoveAll(BOOL bFreeList=TRUE);

	// adding/getting/modifying an element pointer at a given position
	BOOL AddAt(int nPosition,TYPE *pElement);
	TYPE *GetAt(int nPosition) const;
	TYPE * operator[] (int nPosition) const;
	BOOL RemoveAt(int nPosition);
	BOOL ReplaceAt(int nPosition,TYPE *pElement);

	//finding/removing element pointer by order
	TYPE *FindElement(TYPE *pElement,OBJPTRLISTCMPFUNC pCompFunc=NULL);
	BOOL RemoveElement(TYPE *pElement,OBJPTRLISTCMPFUNC pCompFunc=NULL);

	//finding element pointer by order
	int FindElementPos(TYPE *pElement,OBJPTRLISTCMPFUNC pCompFunc=NULL);
	//finding on sorted element pointer list
	int FindPos(TYPE *pElement,OBJPTRLISTCMPFUNC pCompFunc);

	//finding/removing on sorted element pointer list
	void Sort(OBJPTRLISTCMPFUNC pCompFunc);
	BOOL Insert(TYPE *pElement,OBJPTRLISTCMPFUNC pCompFunc);
	TYPE *Find(TYPE *pElement,OBJPTRLISTCMPFUNC pCompFunc);
	BOOL Remove(TYPE *pElement,OBJPTRLISTCMPFUNC pCompFunc);

	TYPE** GetElementList();
public:
	//Free all element pointed in list
	void FreeAll(BOOL bFreeList=FALSE);

	//Delete all element pointed in list
	void DeleteAll(BOOL bFreeList=FALSE);

private:
	//realloc capability
	BOOL ReallocCapability();

private:
	//capability of element pointer buffer list
	int m_nTotalCap;

	//count of expanding element pointer buffer
	int m_cnExpand;

	//count of element pointer
	int m_nCount;

	//element pointer buffer list
	TYPE **m_ppElementList;
};

/////////////////////////////////////////////////////////////////////////////
// CObjPtrList<TYPE> inline functions

template<class TYPE>
inline int CObjPtrList<TYPE>::GetCount() const
{
	return m_nCount;
}

template<class TYPE>
inline int CObjPtrList<TYPE>::GetSize() const
{
	return m_nCount;
}

template<class TYPE>
inline BOOL CObjPtrList<TYPE>::IsEmpty() const
{
	return (m_nCount == 0);
}

template<class TYPE>
inline TYPE *CObjPtrList<TYPE>::GetHead() const
{
	if (m_nCount <= 0)
	{
		return NULL;
	}
	return m_ppElementList[0];
}

template<class TYPE>
inline TYPE *CObjPtrList<TYPE>::GetTail() const
{
	if (m_nCount <= 0)
	{
		return NULL;
	}
	return m_ppElementList[m_nCount-1];
}

template<class TYPE>
CObjPtrList<TYPE>::CObjPtrList(int cnExpand=10)
{
	m_cnExpand = cnExpand;
	m_nTotalCap = 0;
	m_nCount = 0;
	m_ppElementList = NULL;
}

template<class TYPE>
CObjPtrList<TYPE>::~CObjPtrList()
{
	if(m_ppElementList)
	{
		free(m_ppElementList);
	}
}

template<class TYPE>
void CObjPtrList<TYPE>::SetExpandCount(int cnExpand, int cnTotal)
{
	if (cnExpand > 0)
	{
		m_cnExpand = cnExpand;
	}
	else if (cnTotal > 0)
	{
		m_cnExpand = 0x00002000;//8192
		DWORD dwCount = 0x00000010;//16
		while((int)dwCount < m_cnExpand)//
		{
			if (cnTotal <= (int)dwCount)
			{
				m_cnExpand = dwCount;
				break;
			}
			dwCount <<= 1;
		}
	}
}

template<class TYPE>
BOOL CObjPtrList<TYPE>::RemoveHead()
{
	if (m_nCount == 0)
	{
		return FALSE;
	}
	memmove(m_ppElementList,m_ppElementList+1,(m_nCount-1)*sizeof(TYPE *));
	m_nCount--;
	return TRUE;
}

template<class TYPE>
BOOL CObjPtrList<TYPE>::RemoveTail()
{
	if (m_nCount == 0)
	{
		return FALSE;
	}
	m_nCount--;
	return TRUE;
}

template<class TYPE>
BOOL CObjPtrList<TYPE>::AddHead(TYPE *pElement)
{
	if (!ReallocCapability())
	{
		return FALSE;
	}
	memmove(m_ppElementList+1,m_ppElementList,m_nCount*sizeof(TYPE *));
	m_ppElementList[0]=pElement;
	m_nCount++;
	return TRUE;
}

template<class TYPE>
BOOL CObjPtrList<TYPE>::AddTail(TYPE *pElement)
{
	if (!ReallocCapability())
	{
		return FALSE;
	}
	m_ppElementList[m_nCount++]=pElement;
	return TRUE;
}

template<class TYPE>
BOOL CObjPtrList<TYPE>::RemoveAll(BOOL bFreeList=TRUE)
{
	if (bFreeList)
	{
		if (m_ppElementList)
		{
			free(m_ppElementList);
		}
		m_ppElementList = NULL;
		m_nTotalCap = 0;
	}
	m_nCount = 0;
	return TRUE;
}

template<class TYPE>
BOOL CObjPtrList<TYPE>::AddAt(int nPosition,TYPE *pElement)
{
	if (nPosition <= 0)
	{
		return AddHead(pElement);
	}
	if (nPosition >= m_nCount)
	{
		return AddTail(pElement);
	}
	if (!ReallocCapability())
	{
		return FALSE;
	}
	memmove(m_ppElementList+nPosition+1,m_ppElementList+nPosition,(m_nCount-nPosition)*sizeof(TYPE *));
	m_ppElementList[nPosition]=pElement;
	m_nCount++;
	return TRUE;
}

template<class TYPE>
inline TYPE *CObjPtrList<TYPE>::GetAt(int nPosition) const
{
	if (nPosition<0 || nPosition>=m_nCount)
	{
		return NULL;
	}
	return m_ppElementList[nPosition];
}

template<class TYPE>
inline TYPE *CObjPtrList<TYPE>::operator [](int nPosition) const
{
	if (nPosition<0 || nPosition>=m_nCount)
	{
		return NULL;
	}
	return m_ppElementList[nPosition];
}

template<class TYPE>
BOOL CObjPtrList<TYPE>::RemoveAt(int nPosition)
{
	if (nPosition<0 || nPosition>=m_nCount)
	{
		return FALSE;
	}
	memmove(m_ppElementList+nPosition,m_ppElementList+nPosition+1,(m_nCount-nPosition-1)*sizeof(TYPE *));
	m_nCount--;
	return TRUE;
}

template<class TYPE>
BOOL CObjPtrList<TYPE>::ReplaceAt(int nPosition,TYPE *pElement)
{
	if (nPosition < 0 || nPosition >= m_nCount)
	{
		return FALSE;
	}
	m_ppElementList[nPosition]=pElement;
	return TRUE;
}

template<class TYPE>
int CObjPtrList<TYPE>::FindElementPos(TYPE *pElement,OBJPTRLISTCMPFUNC pCompFunc=NULL)
{
	if (m_nCount <= 0)
	{
		return -1;
	}
	for (int i=0;i<m_nCount;i++)
	{
		if (pCompFunc == NULL)
		{
			if (m_ppElementList[i] == pElement)
			{
				return i;
			}
		}
		else
		{
			if (pCompFunc(&m_ppElementList[i],&pElement)==0)
			{
				return i;
			}
		}
	}
	return -1;
}

template<class TYPE>
TYPE *CObjPtrList<TYPE>::FindElement(TYPE *pElement,OBJPTRLISTCMPFUNC pCompFunc=NULL)
{
	int nPosition = FindElementPos(pElement,pCompFunc);
	if (nPosition < 0)
	{
		return NULL;
	}
	return m_ppElementList[nPosition];
}

template<class TYPE>
BOOL CObjPtrList<TYPE>::RemoveElement(TYPE *pElement,OBJPTRLISTCMPFUNC pCompFunc=NULL)
{
	int nPosition = FindElementPos(pElement,pCompFunc);
	if (nPosition < 0)
	{
		return FALSE;
	}
	return RemoveAt(nPosition);
}

template<class TYPE>
void CObjPtrList<TYPE>::Sort(OBJPTRLISTCMPFUNC pCompFunc)
{
	if (m_nCount > 0)
	{
		qsort(m_ppElementList,m_nCount,sizeof(TYPE *),pCompFunc);
	}
}

template<class TYPE>
BOOL CObjPtrList<TYPE>::Insert(TYPE *pElement,OBJPTRLISTCMPFUNC pCompFunc)
{
	if (m_nCount == 0)
	{
		return AddTail(pElement);
	}

	TYPE *pElementTmp;
	if (m_nCount == 1)
	{
		pElementTmp = GetHead();
		if (pCompFunc(&pElement,&pElementTmp) <= 0)
		{
			return AddHead(pElement);
		}
		return AddTail(pElement);
	}
	int n1 = 0;
	int n2 = m_nCount-1;
	pElementTmp = GetAt(n1);
	if (pCompFunc(&pElement,&pElementTmp) <= 0)
	{
		return AddHead(pElement);
	}
	pElementTmp = GetAt(n2);
	if (pCompFunc(&pElement,&pElementTmp) >= 0)
	{
		return AddTail(pElement);
	}

	while (TRUE)
	{
		if (n1+1 == n2)
		{
			return AddAt(n2,pElement);
		}
		int n = n1+(n2-n1)/2;
		pElementTmp = GetAt(n);
		int nRet = pCompFunc(&pElement,&pElementTmp);
		if (nRet == 0)
		{
			return AddAt(n,pElement);
		}
		else if (nRet<=0)
		{
			n2 = n;
		}
		else
		{
			n1 = n;
		}
	}
	return FALSE;
}

template<class TYPE>
int CObjPtrList<TYPE>::FindPos(TYPE *pElement,OBJPTRLISTCMPFUNC pCompFunc)
{
	if (m_nCount <= 0)
	{
		return -1;
	}
	DWORD *pdw = (DWORD *)bsearch(&pElement,m_ppElementList,m_nCount,sizeof(TYPE *),pCompFunc);
	if (pdw == NULL)
	{
		return -1;
	}
	return (int)(pdw-(DWORD *)m_ppElementList);
}

template<class TYPE>
TYPE *CObjPtrList<TYPE>::Find(TYPE *pElement,OBJPTRLISTCMPFUNC pCompFunc)
{
	int nPosition = FindPos(pElement,pCompFunc);
	if (nPosition < 0)
	{
		return NULL;
	}
	return m_ppElementList[nPosition];
}

template<class TYPE>
BOOL CObjPtrList<TYPE>::Remove(TYPE *pElement,OBJPTRLISTCMPFUNC pCompFunc)
{
	int nPosition = FindPos(pElement,pCompFunc);
	if (nPosition < 0)
	{
		return FALSE;
	}
	return RemoveAt(nPosition);
}

template<class TYPE>
void CObjPtrList<TYPE>::FreeAll(BOOL bFreeList=FALSE)
{
	for (int i=0; i<m_nCount; i++)
	{
		free(m_ppElementList[i]);
	}
	RemoveAll(bFreeList);
}

template<class TYPE>
void CObjPtrList<TYPE>::DeleteAll(BOOL bFreeList=FALSE)
{
	for (int i=0; i<m_nCount; i++)
	{
		delete m_ppElementList[i];
	}
	RemoveAll(bFreeList);
}

template<class TYPE>
BOOL CObjPtrList<TYPE>::ReallocCapability()
{
	if (m_nTotalCap > m_nCount)
	{
		return TRUE;
	}
	TYPE **ppElementList = (TYPE **)realloc(m_ppElementList,(m_nTotalCap+m_cnExpand)*sizeof(TYPE *));
	if (ppElementList == NULL)
	{
		return FALSE;
	}

	m_ppElementList = ppElementList;
	m_nTotalCap += m_cnExpand;
	return TRUE;
}

template<class TYPE>
TYPE** CObjPtrList<TYPE>::GetElementList()
{
	return m_ppElementList;
}

template<class TYPE>
BOOL CObjPtrList<TYPE>::CloneFrom(CObjPtrList<TYPE> &listSrc, int nHead, int nTail)
{
	m_nCount = 0;
	if(nTail == 0)
	{
		nTail = listSrc.GetCount();
	}
	if(nTail == 0)
	{
		return TRUE;
	}
	if(m_cnExpand < nTail - nHead)
	{
        m_cnExpand = nTail - nHead;
	}
	if(!ReallocCapability())
	{
		return FALSE;
	}
	TYPE **ppElementList = listSrc.GetElementList();
    memcpy(m_ppElementList,  &ppElementList[nHead], sizeof(TYPE *) * (nTail - nHead));
	m_nCount = nTail - nHead;
    return TRUE;
}

#endif // !defined(_OBJPTRLIST_H__)
